//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-18.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#define INF 999999

/*测试数据
 *6 9
 1 2 1
 1 3 12
 2 3 9
 2 4 3
 3 5 5
 4 3 4
 4 5 13
 4 6 15
 5 6 4
*/

typedef struct path{
	int idx;
	struct path *father;
}Path;

void printMatrix(int *martix, int m, int n){
	for (int i=1; i<m; i++) {
		for (int j=1; j<n; j++) {
			printf("%-6d ",*(martix+m*i+j));
		}
		
		printf("\n");
	}
	
	printf("\n");
}

int main(int argc, const char * argv[])
{
	int v,e;//顶点数，边数
	scanf("%d %d",&v,&e);
	
	int matrix[v+1][v+1];
	
	//初始化
	for (int i=0; i<=v; i++) {
		
		for (int j=0; j<=v; j++) {
			
			if (i==0 || j==0 || i==j) {
				matrix[i][j] = 0;
			}
			else{
				matrix[i][j] = INF;
			}
		}
	}
	
	//读入边
	for (int i=0; i<e; i++) {
		int t1,t2,t3;
		scanf("%d %d %d",&t1,&t2,&t3); //t1 到 t2, 的距离 t3
		matrix[t1][t2] = t3;
	}
	
	
	//printMatrix(&matrix[0][0], v+1, v+1);
	
	int src,dst;
	printf("intput the start and arrive point:\n");
	scanf("%d %d",&src,&dst);
	
	//初始化dis数组
	int dis[v+1];
	int flags[v+1];
	for (int i=0; i<=v; i++) {
		flags[i] = 0;
		dis[i] = matrix[src][i];
	}
	
	
	//初始化路径指针
	Path pathes[v+1];
	for (int i=0; i<=v; i++) {
		pathes[i].idx = i;
		pathes[i].father = NULL;
	}
	
	int u = 0;
	for (int i=1; i<v; i++) { //n-1趟
		
		int min = INF;
		
		//找到距离最短的位置
		for (int j=1; j<=v; j++) {
			if(flags[j]==0 && dis[j] < min){
				min = dis[j];
				u = j;
			}
		}
		
		flags[u] = 1;//标记为确定值
		
		for (int k=1; k<=v; k++) {
			
			if (matrix[u][k] < INF) {//找到u到其他源点有路径的其他点
				
				if(dis[k] > dis[u] + matrix[u][k]){ //指定源点 到k点的距离大于通过 确定点u点 中转到该k点距离时
					dis[k] = dis[u] + matrix[u][k];
					pathes[k].father = &pathes[u];
				}
			}
		}
	}
	
	//打印最短路径
	printf("the shortest distances are:");
	for (int i= 1; i<=v; i++) {
		printf("%d ", dis[i]);
	}
	printf("\n");
	
	printf("the shortest distance is %d \n",dis[dst]);
	printf("the shortest path is:");
	printf("%d",dst);

	Path *pa = pathes[dst].father;
	while (pa) {
		printf(" <- %d",pa->idx);
		pa = pa->father;
	}
	printf(" <- %d \n",src);
	
	
	return 0;
}


